package pro.softzhang.algo.lc1200;

import pro.softzhang.algo.flag.book.BDaily;
import pro.softzhang.algo.flag.theme.TMath;

/**
 *
 */
@BDaily
@TMath
public class LC1250_CheckIfItIsAGoodArray {
    public static void main(String[] args) {

    }

    /**
     * 裴蜀定理
     */
    static
    class Solution {
        public boolean isGoodArray(int[] nums) {
            int divisor = nums[0];
            for (int num : nums)
                if ((divisor = greatestCommonDivisor(divisor, num)) == 1)
                    break;
            return divisor == 1;
        }

        /**
         * 最大公约数，GCD
         * @return
         */
        private int greatestCommonDivisor(int a, int b) {
            while (b != 0) {
                int t = a;
                a = b;
                b = t % b;
            }
            return a;
        }
    }
}
